// N+1Feet
#include <vector>
#include <iostream>

using namespace std;

// queue 队伍中的人数
// 返回值，表示排队的方法
int solution(vector<int> queue) {
  if (queue.size() == 30) {
    // 队伍排满了，这是一种可行的方法
    return 1;
  }

  // 没有排满的情况  
  int result = 0; // 排队的方法数量
  vector<int> copy = queue;
  // 无条件加一个男生
  copy.push_back(1);

  result = solution(copy); // 多了一个男生之后继续排队
  // result - 无条件新增一个男生之后的排队方法

  // 如果当前 queue 末尾是男生，就可以再加一个女生
  copy = queue;
  if (copy.back() == 1) {
    copy.push_back(0);
    result += solution(copy);
  }

  return result;
}

int main(int argc, char const *argv[])
{
  /* code */
  cout << solution({1}) + solution({0}) << endl;
  return 0;
}
